package com.tgy.algorithm.base;


import java.util.Arrays;

public class _堆排序02 {

    public static void heapInsert(int[] nums, int index) {

//        if (nums==null||nums.length==0) {
//            return;
//        }
//
//        nums[index]=num;

        // 1,2,
        //      0,
        //   1     ,2
        // 3
        // 当前值大于父元素的值，才往上走
        while (nums[index] > nums[(index - 1) / 2]) {
            int parent = (index - 1) >> 1;
            swap(nums, index, parent);
            index = parent;
        }
    }

    public static void heapify(int[] nums,int startIndex,int size) {

        // 使用传递进来的值，可以设置其实的往下走的index
        int index = startIndex;
        while (true) {
            int leftIndex = (index << 1) + 1;
            // 左子树已经超出了范围，直接break退出循环
            if (leftIndex >= size) {
                break;
            }
            int largest =  (leftIndex + 1 < size) &&  (nums[leftIndex + 1] > nums[leftIndex]) ? leftIndex + 1 : leftIndex;

            // 父元素的值大于子元素任何一个值，直接退出，这个时候这个有效范围内都是大根堆
            if (nums[index] > nums[largest]) {
                break;
            }
            swap(nums, index, largest);
            index = largest;
        }

    }

    public static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    public static void heapSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        /**
         *              3
         *          2        3
         *      2     1   4     6
         *    5
         */

//        for (int i = 0; i < nums.length; i++) {
//            heapInsert(nums, i);
//        }

        // 这里能使用的必须是所有数都确定了才能使用
        for(int i = nums.length; i > 0; i--) {
            heapify(nums, i - 1, nums.length);
        }


//        swap();
        /**
         *              6
         *          5       4
         *       2    1   3    3
         *     2
         */
        System.out.println(Arrays.toString(nums));


        // n* log(n)
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            heapify(nums,0, i);
        }
    }


    public static void main(String[] args) {

        int[] nums = new int[]{3, 2, 3, 2, 1, 4, 6, 5};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}
